package B刷题.暴力递归.A回溯;

/**
 * @author wei.zhao
 * @description: 37.解数独
 * @date 2022年04月08日 14:27
 */
public class Code10_SolveSudoku {

    /**
     * 思路：
     * 1.从第1行、第1列开始，依次往后放(1,9)之间的数字；
     * 2.所有位置放结束，返回；
     * 3.当前位置不为空，跳到下一个；
     * 4.当前位置为空，判断当前数字是否满足条件，满足条件继续下一个；
     * 注意：
     * 1.重置之前的状态；
     * 2.定义全局变量（是否放满），一旦为true立刻return，置为true一定是在process之后，所以在process之后判断，也能防止最后一个位置被重置为空。
     */
    boolean result = false;

    public void solveSudoku(char[][] board) {
        process(board, 0, 0);
    }

    private void process(char[][] board, int rNum, int cNum) {
        // 最后一行、最后一列放完，返回
        if (rNum == board.length) {
            result = true;
            return;
        }
        if (isBlank(board, rNum, cNum)) {
            for (int i = 1; i <= 9; i++) {
                if (isValid(board, rNum, cNum, (char) (i + 48))) {
                    board[rNum][cNum] = (char) (i + 48);
                    if (cNum >= board.length - 1) {
                        process(board, rNum + 1, 0);
                    } else {
                        process(board, rNum, cNum + 1);
                    }
                    if (result) {
                        return;
                    }
                    board[rNum][cNum] = '.';
                }
            }
        } else {
            if (cNum >= board.length - 1) {
                process(board, rNum + 1, 0);
            } else {
                process(board, rNum, cNum + 1);
            }
        }
    }

    private boolean isValid(char[][] board, int rNum, int cNum, char value) {
        for (char c : board[rNum]) {
            if (c == value) {
                return false;
            }
        }
        for (int i = 0; i < board.length; i++) {
            if (board[i][cNum] == value) {
                return false;
            }
        }
        int rMin = rNum / 3 * 3;
        int rmax = rMin + 3;
        int lmin = cNum / 3 * 3;
        int lmax = lmin + 3;
        for (int i1 = rMin; i1 < rmax; i1++) {
            for (int i2 = lmin; i2 < lmax; i2++) {
                if (board[i1][i2] == value) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean isBlank(char[][] board, int rNum, int cNum) {
        return board[rNum][cNum] == '.';
    }

}
